#
# @lc app=leetcode.cn id=108 lang=python3
#
# [108] 将有序数组转换为二叉搜索树
#

# @lc code=start
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def ArrayToBST(l,r,newNode):
                mid = (r - l)//2
                if l > (l+mid-1):
                    newNode.left = None
                else:
                    newNode.left = TreeNode()
                    ArrayToBST(l, l + mid - 1, newNode.left) #左子树
                newNode.val = nums[l+mid]
                if (l+mid+1) > r:
                    newNode.right = None
                else:
                    newNode.right = TreeNode()
                    ArrayToBST(l+ mid + 1, r, newNode.right) #右子树
                return
        
        newTree = TreeNode()
        numLen = len(nums) 
        ArrayToBST(0,numLen-1,newTree)
        
        return newTree      
 
# @lc code=end

